/*
* Copyright (c) 2003, the JUNG Project and the Regents of the University 
* of California
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* http://jung.sourceforge.net/license.txt for a description.
*/
package edu.uci.ics.jung.algorithms.cluster;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.apache.commons.collections15.Transformer;

import edu.uci.ics.jung.graph.UndirectedGraph;

/**
 * Finds all biconnected components (bicomponents) of an undirected graph. A
 * graph is a biconnected component if at least 2 vertices must be removed in
 * order to disconnect the graph. (Graphs consisting of one vertex, or of two
 * connected vertices, are also biconnected.) Biconnected components of three or
 * more vertices have the property that every pair of vertices in the component
 * are connected by two or more vertex-disjoint paths.
 * <p>
 * Running time: O(|V| + |E|) where |V| is the number of vertices and |E| is the
 * number of edges
 * 
 * @see "Depth first search and linear graph algorithms by R. E. Tarjan (1972), SIAM J. Comp."
 * 
 * @author Joshua O'Madadhain
 */
public class BicomponentClusterer<V, E>
		implements Transformer<UndirectedGraph<V, E>, Set<Set<V>>> {
	protected Map<V, Number> dfs_num;
	protected Map<V, Number> high;
	protected Map<V, V> parents;
	protected Stack<E> stack;
	protected int converse_depth;

	/**
	 * Constructs a new bicomponent finder
	 */
	public BicomponentClusterer() {
	}

	/**
	 * Extracts the bicomponents from the graph.
	 * 
	 * @param theGraph
	 *            the graph whose bicomponents are to be extracted
	 * @return the <code>ClusterSet</code> of bicomponents
	 */
	@Override
	public Set<Set<V>> transform(UndirectedGraph<V, E> theGraph) {
		Set<Set<V>> bicomponents = new LinkedHashSet<Set<V>>();

		if (theGraph.getVertices().isEmpty()) {
			return bicomponents;
		}

		// initialize DFS number for each vertex to 0
		dfs_num = new HashMap<V, Number>();
		for (V v : theGraph.getVertices()) {
			dfs_num.put(v, 0);
		}

		for (V v : theGraph.getVertices()) {
			if (dfs_num.get(v).intValue() == 0) // if we haven't hit this vertex
												// yet...
			{
				high = new HashMap<V, Number>();
				stack = new Stack<E>();
				parents = new HashMap<V, V>();
				converse_depth = theGraph.getVertexCount();
				// find the biconnected components for this subgraph, starting
				// from v
				findBiconnectedComponents(theGraph, v, bicomponents);

				// if we only visited one vertex, this method won't have
				// ID'd it as a biconnected component, so mark it as one
				if (theGraph.getVertexCount() - converse_depth == 1) {
					Set<V> s = new HashSet<V>();
					s.add(v);
					bicomponents.add(s);
				}
			}
		}

		return bicomponents;
	}

	/**
	 * <p>
	 * Stores, in <code>bicomponents</code>, all the biconnected components that
	 * are reachable from <code>v</code>.
	 * </p>
	 * 
	 * <p>
	 * The algorithm basically proceeds as follows: do a depth-first traversal
	 * starting from <code>v</code>, marking each vertex with a value that
	 * indicates the order in which it was encountered (dfs_num), and with a
	 * value that indicates the highest point in the DFS tree that is known to
	 * be reachable from this vertex using non-DFS edges (high). (Since it is
	 * measured on non-DFS edges, "high" tells you how far back in the DFS tree
	 * you can reach by two distinct paths, hence biconnectivity.) Each time a
	 * new vertex w is encountered, push the edge just traversed on a stack, and
	 * call this method recursively. If w.high is no greater than v.dfs_num,
	 * then the contents of the stack down to (v,w) is a biconnected component
	 * (and v is an articulation point, that is, a component boundary). In
	 * either case, set v.high to max(v.high, w.high), and continue. If w has
	 * already been encountered but is not v's parent, set v.high max(v.high,
	 * w.dfs_num) and continue.
	 * 
	 * <p>
	 * (In case anyone cares, the version of this algorithm on p. 224 of Udi
	 * Manber's "Introduction to Algorithms: A Creative Approach" seems to be
	 * wrong: the stack should be initialized outside this method, (v,w) should
	 * only be put on the stack if w hasn't been seen already, and there's no
	 * real benefit to putting v on the stack separately: just check for (v,w)
	 * on the stack rather than v. Had I known this, I could have saved myself a
	 * few days. JRTOM)
	 * </p>
	 * 
	 */
	protected void findBiconnectedComponents(UndirectedGraph<V, E> g, V v,
			Set<Set<V>> bicomponents) {
		int v_dfs_num = converse_depth;
		dfs_num.put(v, v_dfs_num);
		converse_depth--;
		high.put(v, v_dfs_num);

		for (V w : g.getNeighbors(v)) {
			int w_dfs_num = dfs_num.get(w).intValue();// get(w, dfs_num);
			E vw = g.findEdge(v, w);
			if (w_dfs_num == 0) // w hasn't yet been visited
			{
				parents.put(w, v); // v is w's parent in the DFS tree
				stack.push(vw);
				findBiconnectedComponents(g, w, bicomponents);
				int w_high = high.get(w).intValue();// get(w, high);
				if (w_high <= v_dfs_num) {
					// v disconnects w from the rest of the graph,
					// i.e., v is an articulation point
					// thus, everything between the top of the stack and
					// v is part of a single biconnected component
					Set<V> bicomponent = new HashSet<V>();
					E e;
					do {
						e = stack.pop();
						bicomponent.addAll(g.getIncidentVertices(e));
					} while (e != vw);
					bicomponents.add(bicomponent);
				}
				high.put(v, Math.max(w_high, high.get(v).intValue()));
			} else if (w != parents.get(v)) {
				high.put(v, Math.max(w_dfs_num, high.get(v).intValue()));
			}
		}
	}
}
